package com.leetcode.search;

import java.util.Deque;
import java.util.LinkedList;

/**
 * date:
 * description:
 */
public class NumRange {
    public static int[] searchRange(int[] nums, int target) {
        if(nums.length == 0) {
            return new int[]{-1,-1};
        }

        int l = 0, r = nums.length - 1; //二分范围
        while(l < r)			        //查找元素的开始位置
        {
            int mid = (l + r) / 2;
            if(nums[mid] >= target) {
                r = mid;
            }else{
                l = mid + 1;
            }
        }
        if(nums[r] != target) {
            return new int[]{-1,-1}; //查找失败
        }
        int L = r;
        l = 0; r = nums.length - 1;     //二分范围
        while(l < r)			        //查找元素的结束位置
        {
            // 这是个模板，+1的操作背下来
            int mid = (l + r + 1)/2;
            if(nums[mid] <= target) {
                l = mid;
            }else{
                r = mid - 1;
            }
        }
        return new int[]{L,r};
    }

    public int shortestSubarray(int[] A, int K) {
        int N = A.length;
        long[] P = new long[N+1];
        for (int i = 0; i < N; ++i){
            P[i+1] = P[i] + (long) A[i];
        }
        // Want smallest y-x with P[y] - P[x] >= K
        int ans = N+1; // N+1 is impossible
        // 存索引用来计算长度
        Deque<Integer> monoq = new LinkedList();
        for (int y = 0; y < P.length; ++y) {
            // 累积和必须递增，才能留出K的空闲
            while (!monoq.isEmpty() && P[y] <= P[monoq.peekLast()]){
                monoq.removeLast();
            }
            // 缩小左侧范围
            while (!monoq.isEmpty() && P[y] >= P[monoq.peekFirst()] + K){
                ans = Math.min(ans, y - monoq.removeFirst());
            }
            monoq.addLast(y);
        }
        return ans < N+1 ? ans : -1;
    }

    public static void main(String[] args) {

    }
}
